//
// Created by weslywang on 2020/4/29.
//
#include "../common/common.h"

int numDistinct(string s, string t) {
    int numRows=t.length() + 1,zone=s.length() + 1;
    vector<vector<long>> store(t.length() + 1, vector<long>());
    for (int i = 0; i < numRows; i++) {
        store[i].resize(zone);
    }
    for (int i = 0; i <= t.length(); i++) {
        for (int k = 0; k <= s.length(); k++) {
            if (i == 0) {
                store[i][k] = 1;
            } else if (i > k) {
                store[i][k] = 0;
            } else {
                if (t[i - 1] == s[k - 1]) {
                    store[i][k] = store[i][k - 1] + store[i-1][k - 1];
                } else {
                    store[i][k] = store[i][k - 1];
                }
            }
        }
    }
    return store[t.length()][s.length()];
}

int main() {
    Common common;
    int a[] = {1, 2, 3, 4, 5};
    vector<vector<int>> numList = common.loadData();
    cout << numDistinct("rabbbit", "rabbit") << endl;
    return 0;
}